package binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二分搜索树(支持可比较的泛型)
 * 二叉树的原则：
 * 所有比根节点小的数在根节点的左侧（左孩子）
 * 所有比根节点大的树在根节点的右侧（右孩子）
 *
 * @author by Assume
 * @date 2018/8/1 9:43
 */
public class BST<E extends Comparable<E>> {

    // 定义常量用来表示 二叉树的深度 默认值为0（最顶层）
    private static int DEPTH = 0;

    private class Node {
        E e;
        Node left, right;

        /**
         * 提供构造方法
         *
         * @param e 真实元素
         */
        Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private int size;
    /**
     * 根节点
     */
    private Node root;

    /**
     * 提供无参构造
     */
    public BST() {
        root = null;
        size = 0;
    }

    /**
     * 获取当前二分树的大小
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断该树是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 向二叉树中添加元素
     */
    public void add(E e) {

        root = NewAdd(root, e);
    }

    private Node NewAdd(Node node, E e) {
        // 判断当前二分树是否为空
        if (node == null) {
            // 维护size 的大小
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = NewAdd(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = NewAdd(node.right, e);
        }
        return node;
    }

    /**
     * 删除最小值（即树最左最深的节点）
     *
     * @return
     */
    public E removeMin() {
        return removeMin(root).e;
    }

    private Node removeMin(Node node) {
        if (root == null)
            return null;
        Node cur = node;
        Node oldCur = null;
        while (cur.left != null) {
            oldCur = cur;
            cur = cur.left;
        }
        // 将当前cur 的父节点的left 设置为空
        oldCur.left = null;
        return cur;
    }

    /**
     * 删除 最大
     *
     * @return
     */
    public E removeMax() {
        return removeMax(root);
    }

    private E removeMax(Node node) {
        if (node == null)
            return null;
        Node cur = node;
        Node oldCur = null;
        while (cur.right != null) {
            oldCur = cur;
            cur = cur.right;
        }
        oldCur.right = null;
        return cur.e;
    }

    /**
     * 删除任意节点
     */
    // 从二分搜索树中删除元素为e的节点
    public void remove(E e) {
        root = remove(root, e);
    }

    // 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
    // 返回删除节点后新的二分搜索树的根
    Node remove(Node node, E e) {

        if (node == null)
            return null;

        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {   // e.compareTo(node.e) == 0

            // 待删除节点左子树为空的情况
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = new Node(minimum(node.right).e);
            size++;

            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            size--;

            return successor;
        }
    }

    private Node minimum(Node node) {
        if (node.left == null)
            return node;
        return minimum(node.left);
    }


    /**
     * 使用递归算法 实现二叉树添加数据
     *
     * @param node
     * @param e
     */
    @Deprecated
    private void add(Node node, E e) {
        // 判断每个小节点是否存在重复
        if (e.equals(node.e)) {
            return;
        }
        // 判断 该节点存放在左侧还是右侧
        if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            add(node.left, e);
        } else {
            add(node.right, e);
        }
    }

    /**
     * 查看是否包含某元素
     */
    public Boolean contains(E e) {
        return contains(root, e);
    }

    private Boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (e.compareTo(node.e) != 0) {
            // 这里可以分左右 可以优化一大半的算法
            if (e.compareTo(node.e) > 0) {
                return contains(node.right, e);
            } else {
                return contains(node.left, e);
            }
        } else {
            return true;
        }
    }

    /**
     * 二分搜索树 递归前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.e);
        // 递归遍历 左右孩子节点,这里一定要注意左孩子在前面
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 使用栈 实现前序遍历
     */
    public void preOrderByStack() {
        preOrderByStack(root);
    }

    private void preOrderByStack(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        // 有序栈结构先进后出的特性，需要向将右孩子先于左孩子压入栈底
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            System.out.println(pop.e);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }

    /**
     * 二分搜索树 递归中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    /**
     * 栈 实现 中序遍历
     */
    public ArrayList<E> inOrderByStack() {
        return inOrderByStack(root);
    }

    private ArrayList<E> inOrderByStack(Node node) {
        ArrayList<E> result = new ArrayList<>();
        if (node == null) {
            return result;
        }
        Stack<Node> nodeStack = new Stack<>();
        /**
         * 分析：
         *  步骤1：节点如果有左叶子节点，该节点入栈，
         *      如果该节点没有左叶子节点，访问该节点
         *  步骤2：如果节点有右叶子节点，重复步骤1
         *      如果节点没有右叶子节点（说明访问完毕）回退，让栈顶元素出栈，并且访问栈顶元素的右叶子树，重复步骤1
         *  步骤3：当栈为空时，遍历结束
         */
        Node cur = node;
        // 判断 当前节点 是否为空，并且 栈是否遍历完结
        while (cur != null || !nodeStack.empty()) {
            // 将当前节点下所有的左叶子节点压入栈顶
            while (cur != null) {
                nodeStack.push(cur);
                cur = cur.left;// 定义当前变量
            }
            // 获取栈顶元素
            cur = nodeStack.peek();
            result.add(cur.e);
            // 弹出栈顶
            nodeStack.pop();
            cur = cur.right;
        }
        return result;
    }

    /**
     * 二分搜索树 递归后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    /**
     * 栈 实现后序遍历
     *
     * @return
     */
    public ArrayList<E> postOrderByStack() {
        return postOrderByStack(root);
    }

    private ArrayList<E> postOrderByStack(Node node) {
        ArrayList<E> result = new ArrayList<>();
        Stack<Node> nodeStack = new Stack<>();
        Node cur = node;
        while (cur != null || !nodeStack.empty()) {
            /**
             * 分析：
             *  后序遍历 在中序遍历的基础上，需要注意的是：节点的所有右孩子节点访问完毕后，该节点才可以出栈
             */
            // 先遍历所有的左孩子节点
            while (cur != null) {
                nodeStack.push(cur);
                cur = cur.left;
            }
            cur = nodeStack.peek();
            if (cur.right == null) {
                // 当前节点 为左节点的最后一个节点，添加到结果集中，并且将当前cur 设置为栈顶值。
                result.add(cur.e);
                // 该节点 出栈
                nodeStack.pop();
                //判断此时的栈顶的右孩子是否与当前的cur 相等，相等 则说明 该栈顶元素下面的所有元素遍历完毕，需要出栈
                while (!nodeStack.empty() && nodeStack.peek().right.equals(cur)) {
                    cur = nodeStack.peek();
                    result.add(nodeStack.pop().e);
                }
                //将 此时栈顶的右孩子 赋值给cur
                cur = nodeStack.empty() ? null : nodeStack.peek().right;
            } else {
                // 该节点没有左叶子树，但是有右叶子树,将右叶子节点复制给cur
                cur = cur.right;
            }

        }
        return result;
    }

    /**
     * 广度优先遍历（层序遍历） 使用队列
     *
     * @return
     */
    public ArrayList<E> sequenceOrder() {
        return sequenceOrder(root);
    }

    private ArrayList<E> sequenceOrder(Node node) {
        ArrayList<E> result = new ArrayList<>();
        if (node == null)
            return result;
        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(node);
        while (!nodeQueue.isEmpty()) {
            Node cur = nodeQueue.remove();
            result.add(cur.e);
            if (cur.left != null)
                nodeQueue.add(cur.left);
            if (cur.right != null) {
                nodeQueue.add(cur.right);
            }
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBTSString(root, DEPTH, sb);
        return sb.toString();
    }

    /**
     * @param node
     * @param depth 代表二叉树的深度
     * @param sb
     */
    private void generateBTSString(Node node, int depth, StringBuilder sb) {
        // 如果当前二叉树是空的
        if (node == null) {
            sb.append(generateDepthString(depth) + "null\n");
            return;
        }
        sb.append(generateDepthString(depth) + node.e + "\n");
        generateBTSString(node.left, depth + 1, sb);
        generateBTSString(node.right, depth + 1, sb);

    }

    private String generateDepthString(int depth) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            stringBuilder.append("--");
        }
        return stringBuilder.toString();
    }
}